package top.retain;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ivorfan
 * @date 2021/9/9 14:51
 */
public class TreeMaxWidth {
     static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        return bfs(root);
    }

    public int bfs(TreeNode root) {
        Queue<TempNode> q = new LinkedList<>();
        q.offer(new TempNode(root, 0, 0));
        int curDepth = 0, left = 0, res = 0;
        while (!q.isEmpty()) {
            TempNode a = q.poll();
            if (a.node != null) {
                q.offer(new TempNode(a.node.left, a.depth + 1, a.pos * 2));
                q.offer(new TempNode(a.node.right, a.depth + 1, a.pos * 2 + 1));
                if (curDepth != a.depth) {
                    curDepth = a.depth;
                    left = a.pos;
                }
                res = Math.max(res, a.pos - left + 1);
            }
        }
        return res;
    }

    static class TempNode {
        TreeNode node;
        int depth;
        int pos;
        public TempNode(TreeNode node, int depth, int pos) {
            this.node = node;
            this.depth = depth;
            this.pos = pos;
        }
    }

    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            TreeNode root = stringToTreeNode(line);

            int ret = new TreeMaxWidth().widthOfBinaryTree(root);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }
}
